/**
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *后序遍历（Morris遍历）
 *
 */
class PostorderTraversalMorris {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret=new ArrayList<>();
        TreeNode root2=root;
        TreeNode pre=null;
        while(root!=null){
            if(root.left!=null){
                pre=root.left;
                while(pre.right!=null&&pre.right!=root){
                    pre=pre.right;
                }
                if(pre.right==null){
                    pre.right=root;
                    root=root.left;
                  
                }else{
                    pre.right=null;
                    addPath(ret,root.left);//逆序存储当前结点左子树的右边界
                    root=root.right;
                }
            }else{
                root=root.right;
            
            }
        }
        addPath(ret,root2);
        return ret;
    }
    public void addPath(List<Integer> res, TreeNode node){
        int count = 0;
        while (node != null) {
            ++count;
            res.add(node.val);
            node = node.right;
        }
        int left = res.size() - count, right = res.size() - 1;
        while (left < right) {
            int temp = res.get(left);
            res.set(left, res.get(right));
            res.set(right, temp);
            left++;
            right--;
        }


    }
}